package com.cat.dynamicPlanning;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-amount-of-money-robot-can-earn/description/
 * @create 2025/8/31 16:50
 * @since JDK17
 */

public class Solution39 {
    int n, m;
    int[][][] dp;
    int[][] g;

    int dfs(int x, int y, int k) {
        if (x == n - 1 && y == m - 1) {
            if (g[x][y] < 0) {
                if (k == 0) {
                    return g[x][y];
                } else {
                    return 0;
                }
            } else {
                return g[x][y];
            }
        }
        if (x >= n || y >= m) {
            return Integer.MIN_VALUE / 2;
        }
        if (dp[x][y][k] != Integer.MIN_VALUE) {
            return dp[x][y][k];
        }
        int p1, p2, p3 = Integer.MIN_VALUE / 2, p4 = Integer.MIN_VALUE / 2, max;
        if (g[x][y] >= 0) {
            p1 = dfs(x + 1, y, k);
            p2 = dfs(x, y + 1, k);
            max = g[x][y] + Math.max(p1, p2);
        } else {
            if (k > 0) { // 可以感化
                p1 = dfs(x + 1, y, k - 1);
                p2 = dfs(x, y + 1, k - 1);
                p3 = dfs(x + 1, y, k); // 不感化
                p4 = dfs(x, y + 1, k);
                max = Math.max(p1, p2);
                max = Math.max(max, g[x][y] + Math.max(p3, p4));
            } else {
                p1 = dfs(x + 1, y, k); // 不感化
                p2 = dfs(x, y + 1, k);
                max = g[x][y] + Math.max(p1, p2);
            }
        }
        return dp[x][y][k] = max;
    }

    public int maximumAmount(int[][] coins) {
        n = coins.length;
        m = coins[0].length;
        if (n == 1 && m == 1) {
            return coins[0][0] < 0 ? 0 : coins[0][0];
        }
        dp = new int[n][m][3];
        g = coins;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], Integer.MIN_VALUE);
            }
        }
        dfs(0, 0, 2);
        return Arrays.stream(dp[0][0]).max().getAsInt();
    }
}
